<html><head>
<title>Longest Palindrome - Contest of Newbies 2006</title>
<meta content="Longest Palindrome" name="description">
<meta content="document" name="resource-type">
<meta content="global" name="distribution">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta content="MSHTML 6.00.2800.1106" name="GENERATOR">
<meta http-equiv="Content-Style-Type" content="text/css"></head><body>

<table style="page-break-inside: avoid;" border="0" cellpadding="4" cellspacing="3" width="100%">
	<col width="256">
	<col width="256">
	<thead>
		<tr valign="bottom">
			<td bgcolor="#550077" width="100%">
				<p><font color="#ffffff"><font face="Arial Black" size="6">Problem
				D: Longest Palindrome</font></font></p>
<font color="#ffffff">			</font></td>
		</tr>
		<tr valign="bottom">
			<td bgcolor="#550077" width="100%">
				<p align="right"><font color="#ffffff"><font face="Arial Black" size="3">Time
				limit: 10 seconds</font></font></p>
<font color="#ffffff">			</font></td>
		</tr>
	</thead>
</table>

<br>

<p>A <b>palindrome</b> is a string that reads the same from the left as
it does from the right. For example, I, GAG and MADAM are palindromes,
but ADAM is not. Here, we consider also the <i>empty string</i> as a palindrome.

<img src="acm-11151_archivos/p11151.gif" align="right" border="1">

</p><p>From any non-palindromic string, you can always take away some
letters, and get a palindromic subsequence. For example, given the
string ADAM, you remove the letter M and get a palindrome ADA.
</p><p><b>Write a program</b> to determine the length of the longest palindrome you can get from a string.

</p><p></p><h2><a name="SECTION00001000000000000000"><font color="#550077">Input and Output</font></a></h2>

<p>The first line of input contains an integer <b><i>T</i></b> (≤ 60). Each of the next <b><i>T</i></b> lines is a string, whose length is always less than 1000.

</p><p>For ≥90% of the test cases, string length ≤ 255.

</p><p>For each input string, your program should print the length of
the longest palindrome you can get by removing zero or more characters
from it.
</p><p></p><h2><a name="SECTION00003000000000000000"><font color="#550077">Sample Input</font></a></h2>

<pre>2
ADAM
MADAM
</pre>

<p></p><h2><a name="SECTION00004000000000000000"><font color="#550077">Sample Output</font></a></h2>

<pre>3
5
</pre>

<p></p><hr><address>Problemsetter: Raymond Chun</address></body></html>